namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0304. 二维区域和检索 - 矩阵不可变")]
    public class No0304_NumMatrix_SumRegion : AbsBaseTestItem
    {
        /*
        给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
        上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
        示例：
        给定 matrix = [
            [3, 0, 1, 4, 2],
            [5, 6, 3, 2, 1],
            [1, 2, 0, 1, 5],
            [4, 1, 0, 1, 7],
            [1, 0, 3, 0, 5]
        ]
        sumRegion(2, 1, 4, 3) -> 8
        sumRegion(1, 1, 2, 2) -> 11
        sumRegion(1, 2, 2, 4) -> 12
        提示：
            你可以假设矩阵不可变。
            会多次调用 sumRegion 方法。
            你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
        */
        public override void OnTest()
        {
            var matrix = new int[][] {
                new int[] {3, 0, 1, 4, 2},
                new int[] {5, 6, 3, 2, 1},
                new int[] {1, 2, 0, 1, 5},
                new int[] {4, 1, 0, 1, 7},
                new int[] {1, 0, 3, 0, 5}
            };
            var obj1 = new NumMatrix(matrix);
            Assert.TestExe(obj1.SumRegion, 2, 1, 4, 3, 8);
            Assert.TestExe(obj1.SumRegion, 1, 1, 2, 2, 11);
            Assert.TestExe(obj1.SumRegion, 1, 2, 2, 4, 12);

            var obj2 = new NumMatrix_OfficialSolution_TwoDimensionalPrefixSum(matrix);
            Assert.TestExe(obj2.SumRegion, 2, 1, 4, 3, 8);
            Assert.TestExe(obj2.SumRegion, 1, 1, 2, 2, 11);
            Assert.TestExe(obj2.SumRegion, 1, 2, 2, 4, 12);
        }

        /// <summary>
        /// 暴力法
        /// </summary>
        public class NumMatrix
        {
            private readonly int[][] matrix;
            public NumMatrix(int[][] matrix)
            {
                this.matrix = matrix;
            }
            public int SumRegion(int row1, int col1, int row2, int col2)
            {
                int sum = 0;
                for (int r = row1; r <= row2; r++)
                {
                    for (int c = col1; c <= col2; c++)
                    {
                        sum += matrix[r][c];
                    }
                }
                return sum;
            }
        }

        /// <summary>
        /// 官方题解 - 方法二: 二维前缀和
        /// </summary>
        public class NumMatrix_OfficialSolution_TwoDimensionalPrefixSum
        {
            private readonly int[][] sums;
            public NumMatrix_OfficialSolution_TwoDimensionalPrefixSum(int[][] matrix)
            {
                int m = matrix.Length;
                if (m <= 0)
                {
                    sums = new int[][] { };
                    return;
                }
                int n = matrix[0].Length;
                sums = new int[m + 1][];
                sums[0] = new int[n + 1];
                for (int i = 0; i < m; i++)
                {
                    sums[i + 1] = new int[n + 1];
                    for (int j = 0; j < n; j++)
                    {
                        sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                    }
                }
            }
            public int SumRegion(int row1, int col1, int row2, int col2)
            {
                return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
            }
        }
    }
}
